{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#无序表查找\n",
    "def sequentialSearch(alist,item):\n",
    "    pos = 0\n",
    "    found = False\n",
    "    \n",
    "    while pos < len(alist) and not found:\n",
    "        if alist[pos] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            pos = pos + 1\n",
    "    return found\n",
    "\n",
    "testlist = [1,2,32,8,17,19,42,13,9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#有序表查找\n",
    "def orderedSequentialSearch(alist,item):\n",
    "    pos = 0\n",
    "    found = False\n",
    "    stop = False\n",
    "    while pos < len(alist) and not found and not stop:\n",
    "        if alist[pos] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            if alist[pos] > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                pos = pos + 1\n",
    "    return found\n",
    "\n",
    "testlist = [0,1,2,8,13,17,19,32,42]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#二分查找\n",
    "def binarySearch(alist,item):\n",
    "    first = 0\n",
    "    last = len(alist) - 1\n",
    "    found = False\n",
    "    \n",
    "    while first <= last and not found:\n",
    "        midpoint = (first + last)//2\n",
    "        if alist[midpoint] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            if item < alist[midpoint]:\n",
    "                last = midpoint - 1\n",
    "            else:\n",
    "                first = midpoint + 1\n",
    "    return found\n",
    "\n",
    "testlist = [0,1,2,8,13,17,19,32,42]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#二分查找分而治之\n",
    "def binarySearch(alist,item):\n",
    "    if len(alist) == 0:\n",
    "        return False\n",
    "    else:\n",
    "        midpoint = len(alist) // 2\n",
    "        if alist[midpoing] == item:\n",
    "            return True\n",
    "        else:\n",
    "            if item<alist[midpoint]:\n",
    "                return binarySearch(alist[:midpoint],item)\n",
    "            else:\n",
    "                return binarySearch(alist[midpoint+1:],item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "#冒泡排序\n",
    "def bubbleSort(alist):\n",
    "    for passnum in range(len(alist)-1,0,-1):\n",
    "        for i in range(passnum):\n",
    "            if alist[i] > alist[i+1]:\n",
    "                alist[i],alist[i+1] = alist[i+1],alist[i]\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "bubbleSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def shortBubbleSort(alist):\n",
    "    exchanges = True\n",
    "    passnum = len(alist) - 1\n",
    "    while passnum > 1 and exchanges:\n",
    "        exchanges = False\n",
    "        for i in range(passnum):\n",
    "            if alist[i] > alist[i+1]:\n",
    "                exchanges = True\n",
    "                alist[i],alist[i+1] = alist[i+1],alist[i]\n",
    "        passnum = passnum - 1\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "shortBubbleSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "#选择排序\n",
    "def selectionSort(alist):\n",
    "    for fillslot in range(len(alist)-1,0,-1):\n",
    "        positionOfMax = 0\n",
    "        for location in range(1,fillslot+1):\n",
    "            if alist[location]>alist[positionOfMax]:\n",
    "                positionOfMax = location\n",
    "        temp = alist[fillslot]\n",
    "        alist[fillslot] = alist[positionOfMax]\n",
    "        alist[positionOfMax] = temp\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "selectionSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "#插入排序\n",
    "def insertionSort(alist):\n",
    "    for index in range(1,len(alist)):\n",
    "        \n",
    "        currentvalue = alist[index]\n",
    "        position = index                   #新项/插入项\n",
    "        \n",
    "        while position>0 and alist[position-1]>currentvalue:\n",
    "            alist[position] = alist[position-1]\n",
    "            position = position - 1                  #比对和移动\n",
    "        \n",
    "        alist[position] = currentvalue                #插入新项\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "insertionSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]\n",
      "After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]\n",
      "After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]\n",
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "#希尔排序\n",
    "def shellSort(alist):\n",
    "    sublistcount = len(alist)//2       #间隔设定\n",
    "    while sublistcount > 0:\n",
    "        \n",
    "        for startposition in range(sublistcount):               #子列表排序\n",
    "            gapInsertionSort(alist,startposition,sublistcount)\n",
    "        print('After increments of size',sublistcount,'The list is',alist)\n",
    "        \n",
    "        sublistcount = sublistcount // 2     #间隔缩小\n",
    "\n",
    "def gapInsertionSort(alist,start,gap):\n",
    "    for i in range(start+gap,len(alist),gap):\n",
    "        currentvalue = alist[i]\n",
    "        position = i\n",
    "        \n",
    "        while position>=gap and alist[position-gap] > currentvalue:\n",
    "            alist[position] = alist[position-gap]\n",
    "            position = position - gap\n",
    "        alist[position] = currentvalue\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "shellSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "#传统风格归并排序\n",
    "def mergeSort(alist):\n",
    "    if len(alist)>1:                #基本结束条件\n",
    "        mid = len(alist)//2\n",
    "        lefthalf = alist[:mid]\n",
    "        righthalf = alist[mid:]\n",
    "        \n",
    "        mergeSort(lefthalf)            #递归调用\n",
    "        mergeSort(righthalf)\n",
    "        \n",
    "        i= j = k = 0\n",
    "        while i<len(lefthalf) and j<len(righthalf):            #归并过程\n",
    "            if lefthalf[i]<righthalf[j]:\n",
    "                alist[k] = lefthalf[i]\n",
    "                i = i + 1\n",
    "            else:\n",
    "                alist[k] = righthalf[j]\n",
    "                j = j+1\n",
    "            k = k+1\n",
    "        while i<len(lefthalf):                #归并左半部剩余项\n",
    "            alist[k] = lefthalf[i]\n",
    "            i = i+1\n",
    "            k = k+1\n",
    "        while j<len(righthalf):\n",
    "            alist[k] = righthalf[j]\n",
    "            j=j+1\n",
    "            k=k+1\n",
    "            \n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "mergeSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "#python风格归并排序\n",
    "def merge_sort(lst):\n",
    "    if len(lst) <= 1:\n",
    "        return lst\n",
    "    \n",
    "    middle = len(lst) //2\n",
    "    left = merge_sort(lst[:middle])\n",
    "    right = merge_sort(lst[middle:])\n",
    "    \n",
    "    merged = []\n",
    "    while left and right:\n",
    "        if left[0]<right[0]:\n",
    "            merged.append(left.pop(0))\n",
    "        else:\n",
    "            merged.append(right.pop(0))\n",
    "            \n",
    "    merged.extend(right if right else left)\n",
    "    return merged\n",
    "\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "sorted_list = merge_sort(alist)\n",
    "print(sorted_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "#快速排序\n",
    "def quickSort(alist):\n",
    "    quickSortHelper(alist,0,len(alist)-1)\n",
    "\n",
    "def quickSortHelper(alist,first,last):\n",
    "    if first < last:\n",
    "        splitpoint = partition(alist,first,last)\n",
    "        quickSortHelper(alist,first,splitpoint-1)\n",
    "        quickSortHelper(alist,splitpoint+1,last)\n",
    "\n",
    "def partition(alist,first,last):\n",
    "    pivotvalue = alist[first]\n",
    "    leftmark = first+1\n",
    "    rightmark = last\n",
    "    \n",
    "    done = False\n",
    "    while not done:\n",
    "        while leftmark <= rightmark and alist[leftmark]<=pivotvalue:      #向右移动左标\n",
    "            leftmark = leftmark + 1\n",
    "        while alist[rightmark] >=pivotvalue and rightmark>=leftmark:       #向左移动右标\n",
    "            rightmark = rightmark-1\n",
    "        \n",
    "        if rightmark < leftmark:\n",
    "            done = True\n",
    "        else:\n",
    "            temp = alist[leftmark]\n",
    "            alist[leftmark] = alist[rightmark]\n",
    "            alist[rightmark] = temp\n",
    "    temp = alist[first]\n",
    "    alist[first] = alist[rightmark]\n",
    "    alist[rightmark] = temp\n",
    "    \n",
    "    return rightmark\n",
    "alist = [54,26,93,17,77,31,44,55,20]\n",
    "quickSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#哈希 ASC码\n",
    "def hash(astring,tablesize):\n",
    "    sum = 0\n",
    "    for pos in range(len(astring)):\n",
    "        sum = sum + ord(astring[pos])\n",
    "    return sum%tablesize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#\n",
    "class HashTable:\n",
    "    def __init__(self):\n",
    "        self.size = 11\n",
    "        self.slots = [None] * self.size\n",
    "        self.data = [None] * self.size\n",
    "    \n",
    "    def put(self,key,data):\n",
    "        hashvalue = self.hashfunction(key)\n",
    "        \n",
    "        if self.slots[hashvalue] == None:\n",
    "            self.slot[hashvalue] = key\n",
    "            self.data[hashvalue] = data\n",
    "        else:\n",
    "            if self.slot[hashvalue] == key:\n",
    "                self.data[hashvalue] = data         #replace\n",
    "            else:\n",
    "                nextslot = self.rehash(hashvalue)\n",
    "                while self.slots[nextslot] != None and self.slots[nextslot] != key:\n",
    "                    next = self.rehash(nextslot)\n",
    "                \n",
    "                if self.slots[nextslot] == None:\n",
    "                    self.slots[nextslot] = key\n",
    "                    self.data[nextslot] = data\n",
    "                else:\n",
    "                    self.data[nextslot] = data     #replace\n",
    "    def hashfunction(self,key):\n",
    "        return key % self.size\n",
    "    \n",
    "    def rehash(self,oldhash):\n",
    "        return (oldhash + 1) % slef.size\n",
    "    \n",
    "    def get(self,key):\n",
    "        startslot = self.hashfunction(key)\n",
    "        \n",
    "        data = None\n",
    "        stop = False\n",
    "        found = False\n",
    "        position = startslot\n",
    "        while self.slots[position] != None and not found and not stop:\n",
    "            if self.slots[position] == key:\n",
    "                found = True\n",
    "                data = self.data[position]\n",
    "            else:\n",
    "                position = self.rehash(position)\n",
    "                if position == startslot:\n",
    "                    stop = True\n",
    "        return data\n",
    "    \n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)\n",
    "    def __setitem__(self,key,data):\n",
    "        self.put(key,data)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "faker",
   "language": "python",
   "name": "faker"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
